package com.lw.leetcode.bit.b;

/**
 * Created with IntelliJ IDEA.
 * 29. 两数相除
 * 剑指 Offer II 001. 整数除法
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/12 11:49
 */
public class Divide {

    public static void main(String[] args) {
        Divide test = new Divide();
        int a = 18;
        int b = 3;

        int divide = test.divide(a, b);
        System.out.println(divide);
    }

    public int divide(int dividend, int divisor) {
        if (dividend == 0) {
            return 0;
        }
        long a = dividend;
        long b = divisor;
        boolean f1 = a > 0;
        if (!f1) {
            a = ~a + 1;
        }
        boolean f2 = b > 0;
        if (!f2) {
            b = ~b + 1;
        }
        long item = b;
        long c = 1;
        while (item < a) {
            item <<= 1;
            c <<= 1;
        }
        long sum = 0;
        while (a >= b) {
            if (a >= item) {
                a -= item;
                sum += c;
            }
            c >>= 1;
            item >>= 1;
        }
        sum = (f1 ^ f2) ? ~sum + 1 : sum;
        if (sum > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        return (int) sum;
    }
}
